Trong trận Narva, Sheremetev dẫn 5.000 kỵ binh phi tuần tiễu ở hướng tây để dọ thám sự xuất hiện của quân cứu viện Thụy Điển. Khi quân Thụy Điển tấn công chiến hào của quân Nga, Sheremetev không thể điều động kỵ binh dưới quyền chống trả. Những kỵ binh này phần lớn là giới quý tộc Nga và dân Cossack thiếu kỷ luật, trở nên hoảng hốt ngay cả trước khi bị tấn công. Nhìn thấy quân Thụy Điển hùng hổ xông đến, quân Nga quay đầu chạy, cố tìm đường tẩu thoát.

Sau trận thua nhục nhà nãy của Nga, Pyotr Đại đế cố vực dậy tinh thần của quân Nga. Ông viết cho Sheremetev:

Sau trận Narva, Pyotr Đại đế phong Sheremetev làm Tổng Tư lệnh mới của Quân đội Nga được tập trung lại và tái trang bị. Trong hai năm, 1695 và 1696, khi Pyotr dẫn quân tấn công Azov, Sheremetev thực hiện chiến dịch khuấy rối nghi binh ở hướng tây, chiếm được các pháo đài của Tatar ở hạ lưu sông Dnepr.

Sheremetev dẫn quân đến đánh xứ Livonia, được 7.000 quân Thụy Điển bảo vệ dưới quyền chỉ huy của Wolmar Anton von Schlippenbach, và vào tháng 1 năm 1702, giành được một chiến thắng quan trọng. Quân Thụy Điển đã rút vào khu trú đông khi Sheremetev xuất hiện với 8.000 bộ binh và kỵ binh trong trang phục mùa đông được 15 khẩu pháo yểm trợ. Trong trận chiến kéo dài 4 giờ, bên Nga không những đã đuổi quân Thụy Điển ra khỏi doanh trại mùa đông, mà còn gây 1.000 thương vong theo như Thụy Điển nhìn nhận (phía Nga tuyên bố gây thương vong 3.000 và nhìn nhận bị thiệt hại 1.000).

Quan trọng hơn theo ý nghĩa tượng trưng, quân Nga bắt được 350 tù binh Thụy Điển và giải họ về Moskva. Khi nhận được tin, Pyotr Đại đế vô cùng sướng thỏa, thốt lên: "Cảm ơn Thượng đế! Cuối cùng chúng ta đã có thể thắng Thụy Điển." Ông thăng Sheremetev lên nguyên soái (người thứ nhất được phong nguyên hàm này trong quân đội Nga). Ở Moskva, chuông nhà thờ đổ dồn, đại bác bắn chào mừng. Pyotr tổ chức yến tiệc lớn trên Quảng trường Đỏ và ra lệnh bắn pháo bông. Khi tù binh Thụy Điển đến, Pyotr tổ chức đoàn diễu hành để dẫn họ đi vào thành phố. Tinh thần của người Nga, đã xuống thấp từ trận Narva, bây giờ bắt đầu lên.

Mùa hè kế tiếp, tháng 7 năm 1702, Sheremetev lại tấn công Schlippenbach ở Livonia, và lần này đội quân 5.000 người của Thụy Điển bị đánh gần như tan tành: 2.500 thương vong, 300 bị bắt cùng với pháo và cờ xí. Bên Nga bị mất 800 người.

Sau trận này, quân cơ động của Schlippenbach không còn xuất hiện, và cả vùng Livonia xem như bỏ ngỏ ngoại trừ các căn cứ cố định Riga, Pärnu và Dorpat. Quân dưới quyền của Sheremetev tự do tung hoành khắp nơi, đốt phá làng mạc và thị trấn, bắt đi hàng ngàn dân thường.

Mùa thu năm 1702, Pyotr Đại đế ra lệnh cho Sheremetev và Fyodor Matveyevich Apraksin hội quân với ông và quân Cảnh vệ nhằm kiểm soát toàn diện hồ Ladoga bằng cách chiếm lấy pháo đài Thụy Điển ở Nöteborg, nơi hồ Ladoga chảy vào sông Neva.

Nöteborg là một pháo đài kiên cố, khởi đầu được xây vào thế kỷ 14. Bằng cách khống chế cửa sông, nó kiểm soát mọi con đường thương mại từ Biển Baltic đi lên hồ Ladoga và qua hệ thống sông ngòi để vào trong đất liền. Bên nào kiểm soát Nöteborg sẽ kiểm soát con đường thương mại kéo dài đến phương Đông. Khi bị Thụy Điển chiếm vào năm 1611, nó là rào chắn giữa đất Nga và Biển Baltic. Bây giờ, bức tường thành dày và sáu tháp công sự của nó được trang bị với 142 khẩu đại bác. Đội quân trấn giữ chỉ có 450 người, nhưng dòng nước chảy xiết khiến cho tàu thuyền khó tiếp cận ngay cả khi không có đạn pháo rơi lên đầu.

Cuối cùng, quân Nga chiếm được Nöteborg. Pyotr Đại đế vô cùng vui sướng với việc đội quân mới và những khẩu pháo mới làm từ chuông nhà thờ Nga chiếm pháo đài quan trọng đầu tiên từ tay Thụy Điển. Ông đón nhận chiếc chìa khóa từ tay vị chỉ huy Thụy Điển đầu hàng rồi gắn nó lên lô cốt phía tây của pháo đài, và đổi tên của pháo đài thành Schlüsselburg, từ schlüssel trong tiếng Đức có nghĩa là "chìa khóa", cũng có ý nghĩa pháo đài là chìa khóa mở ra Biển Baltic. Sự thất thủ của Nöteborg/Schlüsselburg là thất bại nặng nề cho Thụy Điển vì họ đã mất đi bức tường chắn Nga tiến ra Neva và cả tỉnh Ingria.

Mùa xuân năm sau, 1703, Pyotr dứt khoát "không để mất thời giờ mà Thượng đế đã ban," tấn công trực diện để tạo dựng miền đất Nga trên bờ Biển Baltic. Sheremetev dẫn một cánh quân 20.000 người từ Schlüsselburg xuyên qua khu rừng dọc bờ bắc của con sông Neva để tiến ra biển. Sau chiến thắng của quân Nga ở đây, Pyotr đạt được mục đích – ít nhất là tạm thời – theo đó ông đã tuyên chiến. Ông đã chiếm được trọn chiều dài của sông Neva và lấy lại đường thông ra Biển Baltic. Tỉnh Ingria đã về lại tay người Nga. Trong cuộc diễu hành chiến thắng đi vào Moskva, có một biểu ngữ vẽ bản đồ của Ingria với câu chú thích: "Chúng ta không lấy đất của người khác, mà nhận thừa kế từ tổ tiên ta." Pyotr Đại đế quyết định xây dựng lên thành phố Sankt-Peterburg ở cửa sông Neva.

Ngày 13 tháng 7 năm 1704, Sheremetev chỉ huy 23.000 quân chiếm được Dorpat. Sự thất thủ Dorpat đánh dấu số phận của Narva. Pyotr vội dẫn quân của Sheremetev để tạo nên một đoàn quân gồm 45.000 binh sĩ, trở lại đánh phá và chiếm được Narva ngày 9 tháng 8.

Trong cuộc xâm lăng của Thụy Điển dưới quyền vua Karl XII, Sheremetev được chính thức ghi công cho chiến thắng ở trận Poltava, trận đánh tạo khúc ngoặt cho sự xuống dốc của Thụy Điển và bước đi lên của nước Nga trên thế giới. Đã là nguyên soái, Sheremetev không thể nhận quân hàm nào cao hơn, nên ông nhận nhiều đất làm phần thưởng.

Đây là thời gian để gặt hái thêm chiến công. Sheremetev dẫn tất cả bộ binh và một phần kỵ binh đã đánh Karl XII theo hướng bắc đến Baltic để đánh chiếm pháo đài cảng Riga. Ngày 10 tháng 7 năm 1710, thành phố Riga rộng lớn với 4.500 quân trú phòng rơi vào tay Sheremetev sau cuộc công hãm kéo dài 8 tháng.

Trong cuộc chiến năm 1711 đánh Ottoman, Sheremetev dẫn 22 trung đoàn bộ binh từ vùng Baltic xuống Ukraina để tham gia chiến dịch. Nga bị thất bại nặng nề vì nhiều lý do. Pyotr Đại đế đã từ bỏ chiến lược thận trọng thường thấy lúc trước đã được áp dụng thành công đối với Karl XII. Thay vào đó, ông đã thủ vai trò của Karl mà hung hăng dẫn quân vào Đế chế Ottoman, dựa vào sự hỗ trợ và tiếp việc của một đồng minh không đáng tin cậy. Ông đã nghe thông tin sai lạc về sức mạnh của quân Ottoman, và đã tính toán sai lầm về tốc độ hành quân của họ.